#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define false 0
#define true 1

/*剑指offer58 左旋字符串*/
#if 0
/*
 * 字符串的左旋操作是把字符串前面若干个字符转移到字符串的尾部。
 *
 */
/*
 * 思路1：直接将每个字符一步一步前移。时间复杂度太高，空间复杂度低
 * 思路2：直接将前n个字符保存到缓冲区，然后将后面的字符前移。空间复杂度高，时间复杂度低
 * 思路3：利用字符串反转，先反转前n个字符串，再反转后面的字符串，最后反转全部字符串。
 */
#define BUFFER_SIZE 100

char* reverseLeftWordsQ1(char *s, int n)
{
	char tmp;
	int length = strlen(s);
	
	for(int i = 0; i < n; ++i)
	{
		tmp = s[0];
		for(int j = 0; j < length - 1;++j)
		{
			s[j] = s[j+1];
		}
		s[length - 1] = tmp;
	}

	return s;
}

char* reverseLeftWordsQ2(char *s, int n)
{
	int length = strlen(s);
	char* buffer = (char *)malloc((n+1) * sizeof(char));
	if(buffer == NULL)
		return 0;

	strncpy(buffer,s,n);
	buffer[n]='\0';

	for( int i = n; i < length; ++i)
	{
		s[i - n] = s[i];
	}
	s[length - n] = '\0';

	strcat(s,buffer);
	
	free(buffer);

	return s;
}

char* reverseString(char *s,int start, int end)
{
	char tmp;
	while(start < end)
	{
		tmp = s[start];
		s[start++]=s[end];
		s[end--]=tmp;
	}

	return s;
}

char* reverseLeftWordsQ3(char *s, int n)
{
	int length = strlen(s);
	s = reverseString(s,0,n-1);
	s = reverseString(s,n,length-1);
	s = reverseString(s,0,length-1);	

	return s;
}

int main()
{
	char string[BUFFER_SIZE];
	int count;

	fgets(string,BUFFER_SIZE,stdin);
	count = fgetc(stdin);
	//使用fgets获取标准输入时，会将\n也写入字符串中，需要将其去除
	string[strlen(string) - 1] = '\0';


	printf("%s\n",reverseLeftWordsQ1(string, count));
	printf("%s\n",reverseLeftWordsQ2(string, count));
	printf("%s\n",reverseLeftWordsQ3(string, count));

	
}

#endif

/*125 验证回文子串*/
#if 0
/*
 * 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，忽略字母大小写
 */
/*
 * 思路:用两个指针，分别指向首尾，指针往中间缩进，当指针相遇时结束
 */

#define BUFFER_SIZE 100
int main()
{
	char *start,*end;
	char string[BUFFER_SIZE];
	int length;
	
	fgets(string,BUFFER_SIZE,stdin);

	length = strlen(string);

	start = string;
	end = string + length - 1;

	while(end > start)
	{
		if(!isalnum(*start))
		{
			start++;
			continue;
		}
		if(!isalnum(*end))
		{
			end--;
			continue;
		}
		
		if(tolower(*start) == tolower(*end))
		{
			start++;
			end--;
			continue;
		}
		else
		{
			printf("false\n");
			return false;
		}

	}	

	printf("true\n");
	return true;
}

#endif

/*38 外观数列*/
#if 0
/*
 *给定一个正整数n，输出外观数列的第n项
 *
 */
/*
 * 思路：用两个数组，一个保存当前信息，一个保存下一个信息，然后迭代
 *
 */
#define BUFFER_SIZE 1000
int main()
{
    int n;
    char array[BUFFER_SIZE] = "1";
    char describe[BUFFER_SIZE];
    char compare,tmp[2];
    int count;

    scanf("%d", &n);
    tmp[1] = '\0';

    for (int i = 1; i < n; ++i)
    {
        //对array进行描述，描述信息放在describe
        count = 0;
        compare = array[0];
        describe[0] = '\0';

        for (int j = 0; j <= strlen(array); ++j)
        {
            if (array[j] == compare)
            {
                count++;
            }
            else
            {   //拼接count,array[j-1]
                tmp[0] = (char)('0' + count);
                strcat(describe,&tmp );
                tmp[0] = array[j - 1];
                strcat(describe, &tmp);

                if (j != strlen(array))
                {
                    compare = array[j];
                    count = 1;
                }
            }
        }
        strncpy(array, describe, strlen(describe));
    }

    printf("%s\n", array);
	
    return 0;
}

#endif

/*917 仅仅反转字母*/
#if 0
/*
 * 所有非英文字母保留原有位置
 * 所有英文字母位置反转
 */
/*
 * 思路：遍历字符串，将英文字母交换位置
 */

#define BUFFER_SIZE 1000

int main()
{
    char string[BUFFER_SIZE];
    int start, end;
    int length;
    char tmp;

    fgets(string, BUFFER_SIZE, stdin);
    length = strlen(string);
    string[length - 1] = '\0';

    start = 0;
    end = length - 1;

    while (start < end)
    {
        while(!isalpha(string[start] && start < end))
        {
            start++;
        }
        while (!isalpha(string[end]) && start < end)
        {
            end--;
        }
        tmp = string[start];
        string[start] = string[end];
        string[end] = tmp;

        start++;
        end--;
    }

    printf("%s", string);

    return 0;
}

#endif

/*1437 旅行终点站*/
#if 0
/*
 *给你一份旅游线路图，线路用数组表示，找出旅行的终点站，即没有任何可以通往其他城市的道路
 */
/*
 * 思路：终点站一定在地图的目的地，并且一定不在地图的出发地
 */

char* destCity(char* paths, int pathsSize, int pathsColSize) 
{
    char* des = (char*)malloc((pathsSize + 1) * sizeof(char));

    for (int i = 0; i < pathsColSize; ++i)
    {
        strncpy(des, &paths[i * pathsColSize + (pathsSize + 1)], pathsSize+1);
        for (int j = 0; j < pathsColSize; ++j)
        {
            if (strncmp(des, &paths[j * pathsColSize], pathsSize+1))
            {
                if (j == pathsColSize - 1)
                    return des;

                continue;
            }
            else
            {
                break;//相等则跳出循环
            }
        }
    }
}

int main()
{
    int pathsSize, pathsColSize;
    scanf("%d", &pathsSize);//站点名称长度
    scanf("%d", &pathsColSize);//路径数量

    char* path = (char*)malloc((pathsSize + 1) * pathsColSize * 2 * sizeof(char));

    for (int i = 0; i < pathsColSize; ++i)
    {
        scanf("%s", &path[i* pathsColSize]);
        scanf("%s", &path[i * pathsColSize + (pathsSize + 1)]);
    }
   
    printf("%s",destCity(path, pathsSize, pathsColSize));

    return 0;
}

#endif

/*58 最后一个单词的长度*/
#if 0
/*
 *给定一个字符串，由若干个单词组成，单词用空格隔开，返回最后一个单词的长度。
 */
/*
 *思路：从后往前遍历，用指针指向最后一个单词的首尾即可
 */
#define BUFFER_SIZE 1000
int main()
{
    char string[BUFFER_SIZE],word[BUFFER_SIZE];
    int length,p;
    
    fgets(string, BUFFER_SIZE, stdin);
    length = strlen(string);
    string[length - 1] = '\0';

    p = length - 1;

    if (string[p] == ' ')
    {
        while (string[p] == ' ')
        {
            p--;
        }
    }

    length = p;

    while (string[p] != ' ')
    {
        p--;
    }

    strncpy(word, &string[p+1], length - p);
    word[length - p] = '\0';

    printf("%s\n", word);

    return 0;
}

#endif


